package str;

import java.util.stream.IntStream;

public class KMP {
    private int[] next;
    private String pattern;

    public KMP(String pattern) {
        this.pattern = pattern;
        // 初始化next数组
        next = new int[pattern.length()];
        next[0] = 0;
        // 从第二位开始依次填值
        for (int i = 1, j = 0; i < pattern.length(); i++) {
            // 不相等
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
    }

    /**
     * 进行字符串匹配
     *
     * @param source
     * @return
     */
    public int match(String source) {
        for (int i = 0, j = 0; i < source.length(); i++) {
            while (j > 0 & pattern.charAt(j) != source.charAt(i)) {
                j = next[j - 1];
            }
            if (pattern.charAt(j) == source.charAt(i)) {
                j++;
            }
            if (j == pattern.length()) {
                return i - pattern.length() + 1;
            }
        }

        return -1;
    }

    public void showNext() {
        System.out.println("----------------------------------------------------");
        System.out.println(String.join(",", pattern.split("")));
        StringBuilder sb = new StringBuilder();
        IntStream.of(next).forEach(item -> {
            sb.append(item);
            sb.append(",");
        });
        System.out.println(sb.toString());
        System.out.println("----------------------------------------------------");
    }

    public static void main(String[] args) {
        KMP kmp = new KMP("abcabf");
        kmp.showNext();
        System.out.println(kmp.match("abcabcabf"));
    }
}
